//
// Created by 麻再挺 on 2021/12/20.
//

#include "bst_search.h"

/**
 * 二叉树搜索算法
 * @param t 树
 * @param e 结点
 * @param f 最后一个结点
 * @param p 临时结点
 * @return
 */
bool SearchBST(BstTree t, TElemType e, BstTree f, BstTree *p);

/**
 * 删除结点
 * @param p 树
 */
void Delete(BstTree *p);

bool BST_Insert(BstTree *t, TElemType e) {
    BstTree p = NULL;
    // 如果查找不成功, 则需要插入
    if (!SearchBST(*t, e, NULL, &p)) {
        // 初始化插入结点
        BstTree s = malloc(sizeof(BiTree));
        s->data = e;
        s->lChild = s->rChild = NULL;
        // 如果 p 为NULL, 说明该二叉排序树是空树
        if (!p) {
            *t = s;
        } else if (e < p->data) {
            //如果 p 不为 NULL，则 p 指向的为查找失败的最后一个叶子结点，
            //只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子
            p->lChild = s;
        } else {
            p->rChild = s;
        }
        return TRUE;
    }
    return FALSE;
}

bool SearchBST(BstTree t, TElemType e, BstTree f, BstTree *p) {
    //如果 T 指针为空，说明查找失败，令 p 指针指向查找过程中最后一个叶子结点，并返回查找失败的信息
    if (!t) {
        *p = f;
        return FALSE;
    } else if (e == t->data) {
        // 如果相等，令 p 指针指向该关键字，并返回查找成功信息
        *p = t;
        return TRUE;
    } else if (e < t->data) {
        // 如果 key 值比 T 根结点的值小，则查找其左子树；反之，查找其右子树
        return SearchBST(t->lChild, e, t, p);
    } else {
        return SearchBST(t->rChild, e, t, p);
    }
}

void InOrderBstTraverse(BstTree t) {
    if (t) {
        InOrderBstTraverse(t->lChild);
        printf("%3d", t->data);
        InOrderBstTraverse(t->rChild);
    }
}

bool BST_Delete(BstTree *t, TElemType e) {
    // 不存在关键字等于key的数据元素
    if (!(*t)) {
        return FALSE;
    } else {
        if (e == (*t)->data) {
            Delete(t);
            return TRUE;
        } else if (e < (*t)->data) {
            // 使用递归的方式
            return BST_Delete(&(*t)->lChild, e);
        } else {
            return BST_Delete(&(*t)->rChild, e);
        }
    }
    return TRUE;
}

void Delete(BstTree *p) {
    // 临时变量树
    BstTree q, s;
    // 情况 1: 结点 p 本身为叶子结点
    if (!(*p)->lChild && !(*p)->rChild) {
        *p = NULL;
    } else if (!(*p)->lChild) {
        // 左子树为空，只需用结点 p 的右子树根结点代替结点 p 即可
        q = *p;
        *p = (*p)->rChild;
        free(q);
    } else if (!(*p)->rChild) {
        // 右子树为空，只需用结点 p 的左子树根结点代替结点 p 即可
        q = *p;
        *p = (*p)->lChild;
        free(q);
    } else {
        // 左右子树均不为空, 采用情况 2
        q = *p;
        s = (*p)->lChild;
        // 遍历找到结点 p 的直接前驱
        while (s->rChild) {
            q = s;
            s = s->rChild;
        }
        // 直接改变结点 p 的值
        (*p)->data = (*s).data;
        // 判断结点 p 的左子树 s 是否有右子树，分为两种情况讨论
        if (q != *p) {
            // 若有，则在删除直接前驱结点的同时，令前驱的左孩子结点改为 q 指向结点的孩子结点
            q->rChild = s->lChild;
        } else {
            // 否则，直接将左子树上移即可
            q->lChild = s->lChild;
        }
    }
}

















